package algo.graph;

import java.util.ArrayList;
import java.util.List;

import ds.adt.Digraph;
import ds.adt.Stack;

public class DirectedCycle {

	private boolean[] marked;
	private int[] edgeTo;
	private boolean[] stack;
	private List<Stack<Integer>> cycles;

	public DirectedCycle(Digraph g) {
		this.marked = new boolean[g.V()];
		this.stack = new boolean[g.V()];
		this.edgeTo = new int[g.V()];
		this.cycles = new ArrayList<Stack<Integer>>();

		for (int v = 0; v < g.V(); v++) {
			if (!marked[v]) {
				dfs(g, v);
			}
		}
	}

	private void dfs(Digraph g, int v) {
		marked[v] = true;
		stack[v] = true;
		for (int w : g.adj(v)) {
			if (!marked[w]) {
				edgeTo[w] = v;
				dfs(g, w);
			} else if (stack[w]) { // if the vertex is present in the stack
				// Capture the path of the cycle by tracing the parents using
				// edgeTo
				Stack<Integer> path = new Stack<Integer>();
				for (int x = v; x != w; x = edgeTo[x]) {
					path.push(x);
				}
				path.push(w);
				cycles.add(path);
			}
		}
		stack[v] = false; // reset the stack
	}

	public boolean hasCycle() {
		return (cycles.size() > 0);
	}

	public Iterable<Stack<Integer>> cycles() {
		return cycles;
	}

	public static void main(String[] args) {
		Digraph g = new Digraph(10);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(2, 0);
		g.addEdge(0, 3);
		g.addEdge(0, 4);
		g.addEdge(4, 5);
		g.addEdge(5, 6);
		g.addEdge(6, 4);
		g.addEdge(7, 8);
		g.addEdge(8, 9);
		g.addEdge(9, 7);

		DirectedCycle c = new DirectedCycle(g);
		System.out.println("Graph has cycle ? " + c.hasCycle());
		if (c.hasCycle()) {
			System.out.println("Cycles : ");
			for (Stack<Integer> s : c.cycles()) {
				for (int w : s) {
					System.out.print(w + " ");
				}
				System.out.println();
			}
		}
	}

}
